package top.hkyzf.study.leetcode.array;

import org.junit.Test;

import java.lang.reflect.Array;
import java.util.*;

/**
 * @author 朱峰
 * @date 2022-2-8 11:45
 */
public class 网格照明_1001 {
    // 八个方向
    int[] dX = {-1, -1, 0, 1, 1, 1, 0, -1};
    int[] dY = {0, -1, -1, -1, 0, 1, 1, 1};
    int n = 0;

    // 完全模拟了数组的状态
    public int[] gridIllumination1(int n, int[][] lamps, int[][] queries) {
        this.n = n;
        int[][] grid = new int[n][n];
        int m = queries.length;
        int[] result = new int[m];
        // 初始化点亮的灯
        for (int[] lamp : lamps) {
            lighting(lamp, grid);
        }
        // 查找并关灯（连带周边）
        for (int i = 0; i < m; i++) {
            int[] query = queries[i];
            int ans = turnOffAround(query, grid);
            result[i] = ans;
        }
        return result;
    }

    // 初始化点亮的灯
    private void lighting(int[] lamp, int[][] grid) {
        grid[lamp[0]][lamp[1]] = 2;
        // 检测八个方向灯是否点亮，没有就点亮
        for (int i = 0; i < 8; i++) {
            int newX = lamp[0] + dX[i];
            int newY = lamp[1] + dY[i];
            while (newX >= 0 && newX < n && newY >=0 && newY < n) {
                if (grid[newX][newY] == 0) {
                    grid[newX][newY] = 1;
                }
                newX = newX + dX[i];
                newY = newY + dY[i];
            }
        }
    }

    // 查找并关灯（连带周边）
    private int turnOffAround(int[] query, int[][] grid) {
        int light = grid[query[0]][query[1]];
        // 先判断自己是否亮了
        if (light == 2) {
            // 关灯
            turnOff(query, grid);
        }
        // 检测八个方向是否有灯，有就关闭
        for (int i = 0; i < 8; i++) {
            int newX = query[0] + dX[i];
            int newY = query[1] + dY[i];
            // 关灯
            if (newX >= 0 && newX < n && newY >=0 && newY < n && grid[newX][newY] == 2) {
                turnOff(new int[]{newX, newY}, grid);
            }
        }
        return light == 2 ? 1 : light;
    }

    // 关闭当前传入的灯，并检测照亮范围
    private void turnOff(int[] lamp, int[][] grid) {
        // 先置成 1
        grid[lamp[0]][lamp[1]] = 1;
        // 检测八个方向灯是否点亮，没有就点亮
        for (int i = 0; i < 8; i++) {
            int newX = lamp[0];
            int newY = lamp[1];
            while (newX >= 0 && newX < n && newY >=0 && newY < n) {
                if (grid[newX][newY] == 1 && !check(new int[]{newX, newY}, grid)) {
                    grid[newX][newY] = 0;
                }
                newX = newX + dX[i];
                newY = newY + dY[i];
            }
        }
    }

    // 检查当前灯是否还能被照亮，返回 true，是可以被照亮
    boolean check(int[] lamp, int[][] grid) {
        // 检测八个方向是否有灯
        for (int i = 0; i < 8; i++) {
            int newX = lamp[0] + dX[i];
            int newY = lamp[1] + dY[i];
            while (newX >= 0 && newX < n && newY >=0 && newY < n) {
                if (grid[newX][newY] == 2) {
                    return true;
                }
                newX = newX + dX[i];
                newY = newY + dY[i];
            }
        }
        return false;
    }





    // 只为了解决问题
    public int[] gridIllumination2(int n, int[][] lamps, int[][] queries) {
        int[][] grid = new int[n][n];
        int m = queries.length;
        int[] result = new int[m];
        // 初始化点亮的灯
        for (int[] lamp : lamps) {
            grid[lamp[0]][lamp[1]] = 1;
        }
        for (int[] lamp : grid) {
            System.out.println(Arrays.toString(lamp));
        }
        // 查找并关灯
        for (int i = 0; i < m; i++) {
            int[] query = queries[i];
            int ans = turnOffLight(query, grid);
            result[i] = ans;

            System.out.println();
            for (int[] lamp : grid) {
                System.out.println(Arrays.toString(lamp));
            }
        }
        return result;
    }

    private int turnOffLight(int[] query, int[][] grid) {
        boolean mark = false;
        // 判断自己
        if (grid[query[0]][query[1]] == 1) {
            grid[query[0]][query[1]] = 0;
            mark = true;
        } else {
            if (checkLight(query, grid)) {
                mark = true;
            }
        }
        // 判断周边，灭灯
        for (int i = 0; i < 8; i++) {
            int newX = query[0] + dX[i];
            int newY = query[1] + dY[i];
            if (newX >= 0 && newX < grid.length && newY >=0 && newY < grid.length && grid[newX][newY] == 1) {
                grid[newX][newY] = 0;
            }
        }
        return mark ? 1 : 0;
    }

    // 检查当前灯是否还能被照亮，返回 true，是可以被照亮
    boolean checkLight(int[] lamp, int[][] grid) {
        // 检测八个方向是否有灯
        for (int i = 0; i < 8; i++) {
            int newX = lamp[0] + dX[i];
            int newY = lamp[1] + dY[i];
            while (newX >= 0 && newX < grid.length && newY >=0 && newY < grid.length) {
                if (grid[newX][newY] == 1) {
                    return true;
                }
                newX = newX + dX[i];
                newY = newY + dY[i];
            }
        }
        return false;
    }





    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        Map<Integer, Integer> row = new HashMap<>();
        Map<Integer, Integer> col = new HashMap<>();
        Map<Integer, Integer> diagonal = new HashMap<>();
        Map<Integer, Integer> antiDiagonal = new HashMap<>();
        Set<Long> point = new HashSet<>();
        int[] result = new int[queries.length];
        for (int[] lamp : lamps) {
            // 添加过的点直接跳过
            if (!point.add(hash(lamp[0], lamp[1]))) {
                continue;
            }
            row.put(lamp[0], row.getOrDefault(lamp[0], 0) + 1);
            col.put(lamp[1], col.getOrDefault(lamp[1], 0) + 1);
            diagonal.put(lamp[0]-lamp[1], diagonal.getOrDefault(lamp[0]-lamp[1], 0) + 1);
            antiDiagonal.put(lamp[0]+lamp[1], antiDiagonal.getOrDefault(lamp[0]+lamp[1], 0) + 1);
        }
        for (int i = 0; i < queries.length; i++) {
            // 判断是否亮
            int x = queries[i][0];
            int y = queries[i][1];
            if (row.getOrDefault(x, 0) > 0) {
                result[i] = 1;
            } else if (col.getOrDefault(y, 0) > 0) {
                result[i] = 1;
            } else if (diagonal.getOrDefault(x-y, 0) > 0) {
                result[i] = 1;
            } else if (antiDiagonal.getOrDefault(x+y, 0) > 0) {
                result[i] = 1;
            }
            // 关闭周边的灯
            for (int j = x-1; j <= x+1; j++) {
                for (int k = y-1; k <= y+1; k++) {
                    if (j < 0 || k < 0 || j >= n || k >= n) {
                        continue;
                    }
                    if (point.remove(hash(j, k))) {
                        row.put(j, row.get(j) - 1);
                        col.put(k, col.get(k) - 1);
                        diagonal.put(j-k, diagonal.get(j-k) - 1);
                        antiDiagonal.put(j+k, antiDiagonal.get(j+k) - 1);
                        if (row.get(j) == 0) {
                            row.remove(j);
                        }
                        if (col.get(k) == 0) {
                            col.remove(k);
                        }
                        if (diagonal.get(j-k) == 0) {
                            diagonal.remove(j-k);
                        }
                        if (antiDiagonal.get(j+k) == 0) {
                            antiDiagonal.remove(j+k);
                        }
                    }
                }
            }
        }
        return result;
    }

    public long hash(int x, int y) {
        return (long) x + ((long) y << 32);
    }

    @Test
    public void testGridIllumination () {
        int n = 5;
        int[][] lamps = {{0,0},{4,4}};
        int[][] queries = {{1,4},{1,1}};
        int[] illumination = gridIllumination(n, lamps, queries);
        System.out.println(Arrays.toString(illumination));
    }
}
